{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 解读 `StructuralEqual`\n",
    "\n",
    "源码：`tvm/node/structural_equal.h`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `BaseValueEqual`\n",
    "\n",
    "```c++\n",
    "/*!\n",
    " * \\brief Equality definition of base value class.\n",
    " */\n",
    "class BaseValueEqual {\n",
    " public:\n",
    "  bool operator()(const double& lhs, const double& rhs) const {\n",
    "    // fuzzy float pt comparison\n",
    "    constexpr double atol = 1e-9;\n",
    "    if (lhs == rhs) return true;\n",
    "    double diff = lhs - rhs;\n",
    "    return diff > -atol && diff < atol;\n",
    "  }\n",
    "\n",
    "  bool operator()(const int64_t& lhs, const int64_t& rhs) const { return lhs == rhs; }\n",
    "  bool operator()(const uint64_t& lhs, const uint64_t& rhs) const { return lhs == rhs; }\n",
    "  bool operator()(const int& lhs, const int& rhs) const { return lhs == rhs; }\n",
    "  bool operator()(const bool& lhs, const bool& rhs) const { return lhs == rhs; }\n",
    "  bool operator()(const std::string& lhs, const std::string& rhs) const { return lhs == rhs; }\n",
    "  bool operator()(const DataType& lhs, const DataType& rhs) const { return lhs == rhs; }\n",
    "  template <typename ENum, typename = typename std::enable_if<std::is_enum<ENum>::value>::type>\n",
    "  bool operator()(const ENum& lhs, const ENum& rhs) const {\n",
    "    return lhs == rhs;\n",
    "  }\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`BaseValueEqual` 类，用于比较不同类型的基本值是否相等。该类包含多个重载的 `operator()` 函数，分别用于比较不同类型的参数。\n",
    "\n",
    "具体来说，该类实现了以下类型的比较：\n",
    "- 对于 `double` 类型，使用模糊浮点数比较，允许一定的误差范围（1e-9）。\n",
    "- 对于 `int64_t`、`uint64_t`、`int` 和 `bool` 类型，直接使用等于运算符进行比较。\n",
    "- 对于 `std::string` 类型，也使用等于运算符进行比较。\n",
    "- 对于 `DataType` 类型，同样使用等于运算符进行比较。\n",
    "- 对于枚举类型，也使用等于运算符进行比较。\n",
    "\n",
    "通过这些重载的 `operator()` 函数，可以方便地对不同类型的基本值进行相等性判断。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `ObjectPathPairNode` 和 `ObjectPathPair`\n",
    "\n",
    "```c++\n",
    "/*!\n",
    " * \\brief Pair of `ObjectPath`s, one for each object being tested for structural equality.\n",
    " */\n",
    "class ObjectPathPairNode : public Object {\n",
    " public:\n",
    "  ObjectPath lhs_path;\n",
    "  ObjectPath rhs_path;\n",
    "\n",
    "  ObjectPathPairNode(ObjectPath lhs_path, ObjectPath rhs_path);\n",
    "\n",
    "  static constexpr const char* _type_key = \"ObjectPathPair\";\n",
    "  TVM_DECLARE_FINAL_OBJECT_INFO(ObjectPathPairNode, Object);\n",
    "};\n",
    "\n",
    "class ObjectPathPair : public ObjectRef {\n",
    " public:\n",
    "  ObjectPathPair(ObjectPath lhs_path, ObjectPath rhs_path);\n",
    "\n",
    "  TVM_DEFINE_NOTNULLABLE_OBJECT_REF_METHODS(ObjectPathPair, ObjectRef, ObjectPathPairNode);\n",
    "};\n",
    "```\n",
    "\n",
    "`ObjectPathPairNode` 继承自 `Object` 类，它表示两个对象路径的对（`pair`），用于测试这两个对象的结构相等性。该类包含两个成员变量 `lhs_path` 和 `rhs_path`，分别表示左操作数和右操作数的对象路径。构造函数接受两个 `ObjectPath` 类型的参数，用于初始化这两个成员变量。此外，该类还定义了静态常量字符串 `_type_key`，用于标识该类的类型。\n",
    "\n",
    "`ObjectPathPair` 继承自 `ObjectRef` 类，它表示指向 `ObjectPathPairNode` 对象的引用。该类包含构造函数，接受两个 `ObjectPath` 类型的参数，用于创建 `ObjectPathPairNode` 对象，并将其封装为 `ObjectRef` 类型。此外，该类还定义了一些方法，用于操作 `ObjectPathPairNode` 对象。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `StructuralEqual`\n",
    "\n",
    "```c++\n",
    "/*!\n",
    " * \\brief Content-aware structural equality comparator for objects.\n",
    " *\n",
    " *  The structural equality is recursively defined in the DAG of IR nodes via SEqual.\n",
    " *  There are two kinds of nodes:\n",
    " *\n",
    " *  - Graph node: a graph node in lhs can only be mapped as equal to\n",
    " *    one and only one graph node in rhs.\n",
    " *  - Normal node: equality is recursively defined without the restriction\n",
    " *    of graph nodes.\n",
    " *\n",
    " *  Vars(tir::Var, TypeVar) and non-constant relay expression nodes are graph nodes.\n",
    " *  For example, it means that `%1 = %x + %y; %1 + %1` is not structurally equal\n",
    " *  to `%1 = %x + %y; %2 = %x + %y; %1 + %2` in relay.\n",
    " *\n",
    " *  A var-type node(e.g. tir::Var, TypeVar) can be mapped as equal to another var\n",
    " *  with the same type if one of the following condition holds:\n",
    " *\n",
    " *  - They appear in a same definition point(e.g. function argument).\n",
    " *  - They points to the same VarNode via the same_as relation.\n",
    " *  - They appear in a same usage point, and map_free_vars is set to be True.\n",
    " */\n",
    "class StructuralEqual : public BaseValueEqual {\n",
    " public:\n",
    "  // inheritate operator()\n",
    "  using BaseValueEqual::operator();\n",
    "  /*!\n",
    "   * \\brief Compare objects via strutural equal.\n",
    "   * \\param lhs The left operand.\n",
    "   * \\param rhs The right operand.\n",
    "   * \\param map_free_params Whether or not to map free variables.\n",
    "   * \\return The comparison result.\n",
    "   */\n",
    "  TVM_DLL bool operator()(const ObjectRef& lhs, const ObjectRef& rhs,\n",
    "                          const bool map_free_params = false) const;\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`StructuralEqual` 类，继承自 `BaseValueEqual` 类。该类用于比较两个对象是否在结构上相等。\n",
    "\n",
    "结构相等性是通过 IR 节点的 DAG 递归定义的，有两种类型的节点：\n",
    "- 图节点：在 `lhs` 中的图节点只能映射为 `rhs` 中的一个且仅有一个图节点。\n",
    "- 普通节点：在没有图节点限制的情况下递归定义相等性。\n",
    "\n",
    "`Vars(tir::Var, TypeVar)` 和非常量 relay 表达式节点是图节点。例如，这意味着在 relay 中，`%1 = %x + %y; %1 + %1` 不能被结构地等于 `%1 = %x + %y; %2 = %x + %y; %1 + %2`。\n",
    "\n",
    "如果满足以下条件之一，则可以将类型相同的 `var` 映射为相等：\n",
    "- 它们出现在相同的定义点（例如函数参数）。\n",
    "- 它们通过相同的关系指向相同的 `VarNode`。\n",
    "- 它们出现在相同的使用点，并且将 `map_free_vars` 设置为 `True`。\n",
    "\n",
    "该类还重载了 `operator()` 方法，用于比较两个对象是否在结构上相等。该方法接受三个参数：左操作数、右操作数和布尔值 `map_free_params`，表示是否映射自由变量。返回值为比较结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `SEqualReducer`\n",
    "\n",
    "```C++\n",
    "/*!\n",
    " * \\brief A Reducer class to reduce the structural equality result of two objects.\n",
    " *\n",
    " * The reducer will call the SEqualReduce function of each objects recursively.\n",
    " * Importantly, the reducer may not directly use recursive calls to resolve the\n",
    " * equality checking. Instead, it can store the necessary equality conditions\n",
    " * and check later via an internally managed stack.\n",
    " */\n",
    "class SEqualReducer {\n",
    " private:\n",
    "  struct PathTracingData;\n",
    "\n",
    " public:\n",
    "  /*! \\brief Internal handler that defines custom behaviors.. */\n",
    "  class Handler {\n",
    "   public:\n",
    "    /*!\n",
    "     * \\brief Reduce condition to equality of lhs and rhs.\n",
    "     *\n",
    "     * \\param lhs The left operand.\n",
    "     * \\param rhs The right operand.\n",
    "     * \\param map_free_vars Whether do we allow remap variables if possible.\n",
    "     * \\param current_paths Optional paths to `lhs` and `rhs` objects, for error traceability.\n",
    "     *\n",
    "     * \\return false if there is an immediate failure, true otherwise.\n",
    "     * \\note This function may save the equality condition of (lhs == rhs) in an internal\n",
    "     *       stack and try to resolve later.\n",
    "     */\n",
    "    virtual bool SEqualReduce(const ObjectRef& lhs, const ObjectRef& rhs, bool map_free_vars,\n",
    "                              const Optional<ObjectPathPair>& current_paths) = 0;\n",
    "\n",
    "    /*!\n",
    "     * \\brief Mark the comparison as failed, but don't fail immediately.\n",
    "     *\n",
    "     * This is useful for producing better error messages when comparing containers.\n",
    "     * For example, if two array sizes mismatch, it's better to mark the comparison as failed\n",
    "     * but compare array elements anyway, so that we could find the true first mismatch.\n",
    "     */\n",
    "    virtual void DeferFail(const ObjectPathPair& mismatch_paths) = 0;\n",
    "\n",
    "    /*!\n",
    "     * \\brief Check if fail defferal is enabled.\n",
    "     *\n",
    "     * \\return false if the fail deferral is not enabled, true otherwise.\n",
    "     */\n",
    "    virtual bool IsFailDeferralEnabled() = 0;\n",
    "\n",
    "    /*!\n",
    "     * \\brief Lookup the graph node equal map for vars that are already mapped.\n",
    "     *\n",
    "     *  This is an auxiliary method to check the Map<Var, Value> equality.\n",
    "     * \\param lhs an lhs value.\n",
    "     *\n",
    "     * \\return The corresponding rhs value if any, nullptr if not available.\n",
    "     */\n",
    "    virtual ObjectRef MapLhsToRhs(const ObjectRef& lhs) = 0;\n",
    "    /*!\n",
    "     * \\brief Mark current comparison as graph node equal comparison.\n",
    "     */\n",
    "    virtual void MarkGraphNode() = 0;\n",
    "\n",
    "   protected:\n",
    "    using PathTracingData = SEqualReducer::PathTracingData;\n",
    "  };\n",
    "\n",
    "  /*! \\brief default constructor */\n",
    "  SEqualReducer() = default;\n",
    "  /*!\n",
    "   * \\brief Constructor with a specific handler.\n",
    "   * \\param handler The equal handler for objects.\n",
    "   * \\param tracing_data Optional pointer to the path tracing data.\n",
    "   * \\param map_free_vars Whether or not to map free variables.\n",
    "   */\n",
    "  explicit SEqualReducer(Handler* handler, const PathTracingData* tracing_data, bool map_free_vars)\n",
    "      : handler_(handler), tracing_data_(tracing_data), map_free_vars_(map_free_vars) {}\n",
    "\n",
    "  /*!\n",
    "   * \\brief Reduce condition to comparison of two attribute values.\n",
    "   *\n",
    "   * \\param lhs The left operand.\n",
    "   *\n",
    "   * \\param rhs The right operand.\n",
    "   *\n",
    "   * \\param paths The paths to the LHS and RHS operands.  If\n",
    "   * unspecified, will attempt to identify the attribute's address\n",
    "   * within the most recent ObjectRef.  In general, the paths only\n",
    "   * require explicit handling for computed parameters\n",
    "   * (e.g. `array.size()`)\n",
    "   *\n",
    "   * \\return the immediate check result.\n",
    "   */\n",
    "  bool operator()(const double& lhs, const double& rhs,\n",
    "                  Optional<ObjectPathPair> paths = NullOpt) const;\n",
    "  bool operator()(const int64_t& lhs, const int64_t& rhs,\n",
    "                  Optional<ObjectPathPair> paths = NullOpt) const;\n",
    "  bool operator()(const uint64_t& lhs, const uint64_t& rhs,\n",
    "                  Optional<ObjectPathPair> paths = NullOpt) const;\n",
    "  bool operator()(const int& lhs, const int& rhs, Optional<ObjectPathPair> paths = NullOpt) const;\n",
    "  bool operator()(const bool& lhs, const bool& rhs, Optional<ObjectPathPair> paths = NullOpt) const;\n",
    "  bool operator()(const std::string& lhs, const std::string& rhs,\n",
    "                  Optional<ObjectPathPair> paths = NullOpt) const;\n",
    "  bool operator()(const DataType& lhs, const DataType& rhs,\n",
    "                  Optional<ObjectPathPair> paths = NullOpt) const;\n",
    "\n",
    "  template <typename ENum, typename = typename std::enable_if<std::is_enum<ENum>::value>::type>\n",
    "  bool operator()(const ENum& lhs, const ENum& rhs,\n",
    "                  Optional<ObjectPathPair> paths = NullOpt) const {\n",
    "    using Underlying = typename std::underlying_type<ENum>::type;\n",
    "    static_assert(std::is_same<Underlying, int>::value,\n",
    "                  \"Enum must have `int` as the underlying type\");\n",
    "    return EnumAttrsEqual(static_cast<int>(lhs), static_cast<int>(rhs), &lhs, &rhs, paths);\n",
    "  }\n",
    "\n",
    "  template <typename T, typename Callable,\n",
    "            typename = std::enable_if_t<\n",
    "                std::is_same_v<std::invoke_result_t<Callable, const ObjectPath&>, ObjectPath>>>\n",
    "  bool operator()(const T& lhs, const T& rhs, const Callable& callable) {\n",
    "    if (IsPathTracingEnabled()) {\n",
    "      ObjectPathPair current_paths = GetCurrentObjectPaths();\n",
    "      ObjectPathPair new_paths = {callable(current_paths->lhs_path),\n",
    "                                  callable(current_paths->rhs_path)};\n",
    "      return (*this)(lhs, rhs, new_paths);\n",
    "    } else {\n",
    "      return (*this)(lhs, rhs);\n",
    "    }\n",
    "  }\n",
    "\n",
    "  /*!\n",
    "   * \\brief Reduce condition to comparison of two objects.\n",
    "   * \\param lhs The left operand.\n",
    "   * \\param rhs The right operand.\n",
    "   * \\return the immediate check result.\n",
    "   */\n",
    "  bool operator()(const ObjectRef& lhs, const ObjectRef& rhs) const;\n",
    "\n",
    "  /*!\n",
    "   * \\brief Reduce condition to comparison of two objects.\n",
    "   *\n",
    "   * Like `operator()`, but with an additional `paths` parameter that specifies explicit object\n",
    "   * paths for `lhs` and `rhs`. This is useful for implementing SEqualReduce() methods for container\n",
    "   * objects like Array and Map, or other custom objects that store nested objects that are not\n",
    "   * simply attributes.\n",
    "   *\n",
    "   * Can only be called when `IsPathTracingEnabled()` is `true`.\n",
    "   *\n",
    "   * \\param lhs The left operand.\n",
    "   * \\param rhs The right operand.\n",
    "   * \\param paths Object paths for `lhs` and `rhs`.\n",
    "   * \\return the immediate check result.\n",
    "   */\n",
    "  bool operator()(const ObjectRef& lhs, const ObjectRef& rhs, const ObjectPathPair& paths) const {\n",
    "    ICHECK(IsPathTracingEnabled()) << \"Path tracing must be enabled when calling this function\";\n",
    "    return ObjectAttrsEqual(lhs, rhs, map_free_vars_, &paths);\n",
    "  }\n",
    "\n",
    "  /*!\n",
    "   * \\brief Reduce condition to comparison of two definitions,\n",
    "   *        where free vars can be mapped.\n",
    "   *\n",
    "   *  Call this function to compare definition points such as function params\n",
    "   *  and var in a let-binding.\n",
    "   *\n",
    "   * \\param lhs The left operand.\n",
    "   * \\param rhs The right operand.\n",
    "   * \\return the immediate check result.\n",
    "   */\n",
    "  bool DefEqual(const ObjectRef& lhs, const ObjectRef& rhs);\n",
    "\n",
    "  /*!\n",
    "   * \\brief Reduce condition to comparison of two arrays.\n",
    "   * \\param lhs The left operand.\n",
    "   * \\param rhs The right operand.\n",
    "   * \\return the immediate check result.\n",
    "   */\n",
    "  template <typename T>\n",
    "  bool operator()(const Array<T>& lhs, const Array<T>& rhs) const {\n",
    "    if (tracing_data_ == nullptr) {\n",
    "      // quick specialization for Array to reduce amount of recursion\n",
    "      // depth as array comparison is pretty common.\n",
    "      if (lhs.size() != rhs.size()) return false;\n",
    "      for (size_t i = 0; i < lhs.size(); ++i) {\n",
    "        if (!(operator()(lhs[i], rhs[i]))) return false;\n",
    "      }\n",
    "      return true;\n",
    "    }\n",
    "\n",
    "    // If tracing is enabled, fall back to the regular path\n",
    "    const ObjectRef& lhs_obj = lhs;\n",
    "    const ObjectRef& rhs_obj = rhs;\n",
    "    return (*this)(lhs_obj, rhs_obj);\n",
    "  }\n",
    "  /*!\n",
    "   * \\brief Implementation for equality rule of var type objects(e.g. TypeVar, tir::Var).\n",
    "   * \\param lhs The left operand.\n",
    "   * \\param rhs The right operand.\n",
    "   * \\return the result.\n",
    "   */\n",
    "  bool FreeVarEqualImpl(const runtime::Object* lhs, const runtime::Object* rhs) const {\n",
    "    // var need to be remapped, so it belongs to graph node.\n",
    "    handler_->MarkGraphNode();\n",
    "    // We only map free vars if they corresponds to the same address\n",
    "    // or map free_var option is set to be true.\n",
    "    return lhs == rhs || map_free_vars_;\n",
    "  }\n",
    "\n",
    "  /*! \\return Get the internal handler. */\n",
    "  Handler* operator->() const { return handler_; }\n",
    "\n",
    "  /*! \\brief Check if this reducer is tracing paths to the first mismatch. */\n",
    "  bool IsPathTracingEnabled() const { return tracing_data_ != nullptr; }\n",
    "\n",
    "  /*!\n",
    "   * \\brief Get the paths of the currently compared objects.\n",
    "   *\n",
    "   * Can only be called when `IsPathTracingEnabled()` is true.\n",
    "   */\n",
    "  const ObjectPathPair& GetCurrentObjectPaths() const;\n",
    "\n",
    "  /*!\n",
    "   * \\brief Specify the object paths of a detected mismatch.\n",
    "   *\n",
    "   * Can only be called when `IsPathTracingEnabled()` is true.\n",
    "   */\n",
    "  void RecordMismatchPaths(const ObjectPathPair& paths) const;\n",
    "\n",
    " private:\n",
    "  bool EnumAttrsEqual(int lhs, int rhs, const void* lhs_address, const void* rhs_address,\n",
    "                      Optional<ObjectPathPair> paths = NullOpt) const;\n",
    "\n",
    "  bool ObjectAttrsEqual(const ObjectRef& lhs, const ObjectRef& rhs, bool map_free_vars,\n",
    "                        const ObjectPathPair* paths) const;\n",
    "\n",
    "  static void GetPathsFromAttrAddressesAndStoreMismatch(const void* lhs_address,\n",
    "                                                        const void* rhs_address,\n",
    "                                                        const PathTracingData* tracing_data);\n",
    "\n",
    "  template <typename T>\n",
    "  static bool CompareAttributeValues(const T& lhs, const T& rhs,\n",
    "                                     const PathTracingData* tracing_data,\n",
    "                                     Optional<ObjectPathPair> paths = NullOpt);\n",
    "\n",
    "  /*! \\brief Internal class pointer. */\n",
    "  Handler* handler_ = nullptr;\n",
    "  /*! \\brief Pointer to the current path tracing context, or nullptr if path tracing is disabled. */\n",
    "  const PathTracingData* tracing_data_ = nullptr;\n",
    "  /*! \\brief Whether or not to map free vars. */\n",
    "  bool map_free_vars_ = false;\n",
    "};\n",
    "```\n",
    "\n",
    "`SEqualReducer` 类，它是结构相等性结果的规约器。这个类的主要目的是通过调用每个对象的 `SEqualReduce` 函数来递归地比较两个对象是否相等。\n",
    "\n",
    "`SEqualReducer` 类包含内部处理器 `Handler`，它定义了一些自定义行为的方法，如 `SEqualReduce`、`DeferFail`、`IsFailDeferralEnabled`、`MapLhsToRhs` 和 `MarkGraphNode`。这些方法需要在派生类中实现。\n",
    "\n",
    "`SEqualReducer` 类还包含一些重载的运算符，用于比较不同类型的值，如 `double`、`int64_t`、`uint64_t`、`int`、`bool`、`std::string`、`DataType` 和枚举类型。这些运算符将调用相应的比较方法，如 `EnumAttrsEqual` 或 `ObjectAttrsEqual`。\n",
    "\n",
    "此外，`SEqualReducer` 类还提供了一些其他方法，如 `operator()` 重载，用于比较两个对象是否相等；`DefEqual` 方法，用于比较两个定义点是否相等，其中自由变量可以被映射；以及一些辅助方法，如 `IsPathTracingEnabled` 和 `GetCurrentObjectPaths`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `SEqualHandlerDefault`\n",
    "\n",
    "```c++\n",
    "/*! \\brief The default handler for equality testing.\n",
    " *\n",
    " * Users can derive from this class and override the DispatchSEqualReduce method,\n",
    " * to customize equality testing.\n",
    " */\n",
    "class SEqualHandlerDefault : public SEqualReducer::Handler {\n",
    " public:\n",
    "  SEqualHandlerDefault(bool assert_mode, Optional<ObjectPathPair>* first_mismatch,\n",
    "                       bool defer_fails);\n",
    "  virtual ~SEqualHandlerDefault();\n",
    "\n",
    "  bool SEqualReduce(const ObjectRef& lhs, const ObjectRef& rhs, bool map_free_vars,\n",
    "                    const Optional<ObjectPathPair>& current_paths) override;\n",
    "  void DeferFail(const ObjectPathPair& mismatch_paths) override;\n",
    "  bool IsFailDeferralEnabled() override;\n",
    "  ObjectRef MapLhsToRhs(const ObjectRef& lhs) override;\n",
    "  void MarkGraphNode() override;\n",
    "\n",
    "  /*!\n",
    "   * \\brief The entry point for equality testing\n",
    "   * \\param lhs The left operand.\n",
    "   * \\param rhs The right operand.\n",
    "   * \\param map_free_vars Whether or not to remap variables if possible.\n",
    "   * \\return The equality result.\n",
    "   */\n",
    "  virtual bool Equal(const ObjectRef& lhs, const ObjectRef& rhs, bool map_free_vars);\n",
    "\n",
    " protected:\n",
    "  /*!\n",
    "   * \\brief The dispatcher for equality testing of intermediate objects\n",
    "   * \\param lhs The left operand.\n",
    "   * \\param rhs The right operand.\n",
    "   * \\param map_free_vars Whether or not to remap variables if possible.\n",
    "   * \\param current_paths Optional paths to `lhs` and `rhs` objects, for error traceability.\n",
    "   * \\return The equality result.\n",
    "   */\n",
    "  virtual bool DispatchSEqualReduce(const ObjectRef& lhs, const ObjectRef& rhs, bool map_free_vars,\n",
    "                                    const Optional<ObjectPathPair>& current_paths);\n",
    "\n",
    " private:\n",
    "  class Impl;\n",
    "  Impl* impl;\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "这段代码定义了一个名为`SEqualHandlerDefault`的类，它是`SEqualReducer::Handler`类的默认处理器。这个类用于处理对象之间的相等性测试。\n",
    "\n",
    "该类具有以下成员函数：\n",
    "- `SEqualHandlerDefault(bool assert_mode, Optional<ObjectPathPair>* first_mismatch, bool defer_fails)`：构造函数，接受三个参数：`assert_mode`表示是否使用断言模式，`first_mismatch`是一个指向可选的对象路径对的指针，`defer_fails`表示是否延迟失败。\n",
    "- `~SEqualHandlerDefault()`：析构函数。\n",
    "- `SEqualReduce(const ObjectRef& lhs, const ObjectRef& rhs, bool map_free_vars, const Optional<ObjectPathPair>& current_paths)`：重载的`SEqualReduce`方法，用于比较两个对象是否相等。它接受四个参数：左操作数`lhs`、右操作数`rhs`、是否映射自由变量`map_free_vars`以及当前路径对`current_paths`。\n",
    "- `DeferFail(const ObjectPathPair& mismatch_paths)`：延迟失败的方法，接受一个对象路径对作为参数。\n",
    "- `IsFailDeferralEnabled()`：检查是否启用了失败延迟。\n",
    "- `MapLhsToRhs(const ObjectRef& lhs)`：将左操作数映射到右操作数的方法，接受一个对象引用作为参数。\n",
    "- `MarkGraphNode()`：标记图形节点的方法。\n",
    "- `Equal(const ObjectRef& lhs, const ObjectRef& rhs, bool map_free_vars)`：入口点方法，用于进行相等性测试。它接受三个参数：左操作数`lhs`、右操作数`rhs`以及是否映射自由变量`map_free_vars`。\n",
    "- `DispatchSEqualReduce(const ObjectRef& lhs, const ObjectRef& rhs, bool map_free_vars, const Optional<ObjectPathPair>& current_paths)`：中间对象的相等性测试调度器方法，接受四个参数：左操作数`lhs`、右操作数`rhs`、是否映射自由变量`map_free_vars`以及当前路径对`current_paths`。\n",
    "\n",
    "此外，该类还包含一个私有成员变量`impl`，它是一个指向内部实现类的指针。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python 接口：`structural_equal`\n",
    "\n",
    "```python\n",
    "def structural_equal(lhs, rhs, map_free_vars=False):\n",
    "    \"\"\"Check structural equality of lhs and rhs.\n",
    "\n",
    "    The structural equality is recursively defined in the DAG of IRNodes.\n",
    "    There are two kinds of nodes:\n",
    "\n",
    "    - Graph node: a graph node in lhs can only be mapped as equal to\n",
    "      one and only one graph node in rhs.\n",
    "    - Normal node: equality is recursively defined without the restriction\n",
    "      of graph nodes.\n",
    "\n",
    "    Vars(tir::Var, TypeVar) and non-constant relay expression nodes are graph nodes.\n",
    "    For example, it means that `%1 = %x + %y; %1 + %1` is not structurally equal\n",
    "    to `%1 = %x + %y; %2 = %x + %y; %1 + %2` in relay.\n",
    "\n",
    "    A var-type node(e.g. tir::Var, TypeVar) can be mapped as equal to another var\n",
    "    with the same type if one of the following condition holds:\n",
    "\n",
    "    - They appear in a same definition point(e.g. function argument).\n",
    "    - They points to the same VarNode via the same_as relation.\n",
    "    - They appear in a same usage point, and map_free_vars is set to be True.\n",
    "\n",
    "    The rules for var are used to remap variables occurs in function\n",
    "    arguments and let-bindings.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    lhs : Object\n",
    "        The left operand.\n",
    "\n",
    "    rhs : Object\n",
    "        The left operand.\n",
    "\n",
    "    map_free_vars : bool\n",
    "        Whether free variables (i.e. variables without a definition site) should be mapped\n",
    "        as equal to each other.\n",
    "\n",
    "    Return\n",
    "    ------\n",
    "    result : bool\n",
    "        The comparison result.\n",
    "\n",
    "    See Also\n",
    "    --------\n",
    "    structural_hash\n",
    "    assert_strucural_equal\n",
    "    \"\"\"\n",
    "    lhs = tvm.runtime.convert(lhs)\n",
    "    rhs = tvm.runtime.convert(rhs)\n",
    "    return bool(_ffi_node_api.StructuralEqual(lhs, rhs, False, map_free_vars))  # type: ignore # pylint: disable=no-member\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`structural_equal` 函数，用于检查两个对象（`lhs` 和 `rhs`）在结构上是否相等。\n",
    "\n",
    "该函数接受三个参数：\n",
    "- `lhs`：左操作数，表示要比较的第一个对象。\n",
    "- `rhs`：右操作数，表示要比较的第二个对象。\n",
    "- `map_free_vars`：布尔值，表示是否将自由变量（即没有定义  `site` 的变量）映射为相等。\n",
    "\n",
    "函数首先使用 `tvm.runtime.convert` 将 `lhs` 和 `rhs` 转换为相应的类型。然后，它调用 `_ffi_node_api.StructuralEqual` 函数来执行实际的结构相等性检查，并将结果转换为布尔值返回。\n",
    "\n",
    "该函数的实现考虑了两种类型的节点：图节点和非图节点。图节点是指那些在 `lhs` 中只能映射为与 `rhs` 中的一个且只有一个图节点相等的节点。非图节点则通过递归定义等价性，不受到图节点的限制。\n",
    "\n",
    "对于图节点（如 `tir::Var` 和 `TypeVar`），如果满足以下条件之一，它们可以映射为相同类型的另一个变量相等：\n",
    "- 它们出现在相同的定义点（例如函数参数）。\n",
    "- 它们通过相同的关系指向相同的 `VarNode`。\n",
    "- 它们出现在相同的使用点，并且 `map_free_vars` 设置为 `True`。\n",
    "\n",
    "这些规则用于重新映射函数参数和 `let` 绑定中的变量。\n",
    "\n",
    "最后，函数返回布尔值，表示比较的结果。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "xin",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
